/*************************************************************************
> File Name: radix_sort.c
> Author: icebear
> Mail: 3322366195@qq.com
> Created Time: 2023-07-23 13:29:36
> Description: 基数排序
************************************************************************/
#include "general.h"
#include <stdio.h>
void radixSort(int arr[], int length);
void countSort(int arr[], int length, int exp);
int main(int argc, char const *argv[])
{
    int arr[10] = {9, 4, 2, 7, 5, 1, 8, 3, 6};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    printArr(arr, size);
    radixSort(arr, size);
    printf("Sorted array: \n");
    printArr(arr, size);
}

// 基数排序函数
void radixSort(int arr[], int length)
{
    int max = getArrMax(arr, length);
    // 对每位进行计数排序
    for (int exp = 1; max / exp > 0; exp *= 10)
    {
        countSort(arr, length, exp);
    }
}
// 使用计数排序对数组进行排序
void countSort(int arr[], int length, int exp)
{
    int output[length];  // 存储排序后的结果
    int count[10] = {0}; // 存储每个数字出现的次数
    // 统计每个数字出现的次数
    for (int i = 0; i < length; i++)
    {
        count[(arr[i] / exp) % 10]++;
    }
    // 计算每个数字在排序后的位置
    for (int i = 1; i < 10; i++)
    {
        count[i] += count[i - 1];
    }
    // 将数字放入输出数组中
    for (int i = length - 1; i >= 0; i--)
    {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    // 将排序后的结果复制回原始数组
    for (int i = 0; i < length; i++)
    {
        arr[i] = output[i];
    }
}
